"""
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。


使用广度优先搜索
"""

from typing import List

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix) # type: int
        if m == 0:
            return []
        n = len(matrix[0])
        if n == 0:
            return []
        new_matrix = [[-1] * n for _ in range(m)]
        def validate(x, y):
            return m > x >= 0 and n > y >= 0

        points = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    new_matrix[i][j] = 0
                    points.append((i, j))

        while points:
            x ,y = points.pop()
            # new_points = []
            for px, py in ((x+1, y), (x, y+1), (x-1, y), (x, y-1)):
                if not validate(px, py) or new_matrix[px][py] != -1:
                    continue
                new_matrix[px][py] = new_matrix[x][y] + 1
                points.insert(0, (px, py))

        return new_matrix
if __name__ == "__main__":
    # m = [[0, 0, 0], [1, 1, 1], [1, 1, 1]]
    m = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
    print(Solution().updateMatrix(m))
